package practice.tree.binary;


import struct.BinaryTree;

import java.util.LinkedList;
import java.util.Queue;
import java.util.Stack;

/**
 * 二叉树遍历
 */
public class BinaryTreeTraversaller {
   

    /**
     * 前序递归
     * @param root
     */
    public static void preOrderRecursion(BinaryTree root) {
        if (root == null) {
            return;
        }
        print(root.getValue());
        if (root.getLeftNode() != null) {
            preOrderRecursion(root.getLeftNode());
        }
        if (root.getRightNode() != null) {
            preOrderRecursion(root.getRightNode());
        }
    }

    /**
     * 前序非递归
     * @param root
     */
    public static void preOrderUnRecursion(BinaryTree root) {
        if (root == null) {
            return;
        }
        Stack<BinaryTree> stack = new Stack<>();
        BinaryTree node = root;
        while (node != null || !stack.isEmpty()) {
            //循环访问到最左子节点，并依次入栈
            while (node != null) {
                print(node.getValue());
                stack.push(node);
                node = node.getLeftNode();
            }
            //已到最左子节点，出栈，访问当前父节点的右子树
            if (!stack.isEmpty()) {
                node = stack.pop().getRightNode();

            }
        }

    }

    /**
     * 中序递归
     * @param root
     */
    public static void inOrderRecursion(BinaryTree root) {
        if (root == null) {
            return;
        }
        inOrderRecursion(root.getLeftNode());
        print(root.getValue());
        inOrderRecursion(root.getRightNode());
    }

    /**
     * 中序非递归
     * @param root
     */
    public static void inOrderUnRecursion(BinaryTree root) {
        if (root == null) {
            return;
        }
        BinaryTree node = root;
        Stack<BinaryTree> stack = new Stack<>();

        while (node != null || !stack.isEmpty()) {
            //当前节点入栈，保存左子树
            while (node != null) {
                stack.push(node);
                node = node.getLeftNode();
            }
            //已到最左子节点，出栈并访问当前节点，然后访问当前节点的右子树
            if (!stack.isEmpty()) {
                node = stack.pop();
                print(node.getValue());
                node = node.getRightNode();
            }
        }
    }

    /**
     * 后序递归
     * @param root
     */
    public static void postOrderRecursion(BinaryTree root) {
        if (root == null) {
            return;
        }
        postOrderRecursion(root.getLeftNode());
        postOrderRecursion(root.getRightNode());
        print(root.getValue());
    }

    /**
     * 后序非递归
     * @param root
     */
    public static void postOrderUnRecursion(BinaryTree root) {
        if (root == null) {
            return;
        }
        Stack<BinaryTree> stack = new Stack<>();
        stack.push(root);
        BinaryTree node;
        //记录前一个访问的节点
        BinaryTree preVisit = null;
        while (!stack.isEmpty()) {
            /**
             * 如果栈顶节点木有子节点，访问并出栈
             * 否则前一个访问的节点为其右子节点且不为空，说明该节点的所有子节点已访问过，可以访问栈顶节点并出栈
             * 否则前一个访问的节点为其左子节点，说明该节点的所有子节点已访问过，可以访问栈顶节点并出栈
             * 否则前一个访问的节点并不为栈顶节点的子节点，说明该节点的子节点还未访问，将其子节点入栈
             */
            node = stack.peek();
            if (node.getLeftNode() == null && node.getRightNode() == null ||
                    (preVisit != null && ((node.getRightNode() != null && preVisit == node.getRightNode())) || (node.getRightNode() == null && preVisit == node.getLeftNode()))) {
                print(node.getValue());
                preVisit = node;
                stack.pop();
            } else {
//                  右子节点先入栈，左子节点后入栈，保证左-右-中的访问次序
                if (node.getRightNode() != null) {
                    stack.push(node.getRightNode());
                }
                if (node.getLeftNode() != null) {
                    stack.push(node.getLeftNode());
                }
            }
        }
    }

    /**
     * 层序递归
     * @param root
     * @param linefeed 是否换行
     */
    public static void levelOrderRecursion(BinaryTree root, boolean linefeed) {
        if (root == null) {
            return;
        }
        int level = getLevel(root);
//        循环访问每一层
        for (int i = 1; i <= level; i++) {
            levelOrderRecursion(root, i);
//            访问完一层后换行
            if (linefeed) {
                System.out.println();
            }
        }


    }

    /**
     * 层序递归实际实现，访问根节点的第n层
     * @param root 根节点
     * @param level 层数
     */
    private static void levelOrderRecursion(BinaryTree root, int level) {
        if (root == null) {
            return;
        }
//        已经为第一层，直接访问
        if (level == 1) {
            print(root.getValue());

        } else {
//            访问根节点左子树和右子树
            levelOrderRecursion(root.getLeftNode(), level - 1);
            levelOrderRecursion(root.getRightNode(), level - 1);

        }
    }


    /**
     * 层序非递归
     * @param root
     * @param linefeed
     */
    public static void levelOrderUnRecursion(BinaryTree root, boolean linefeed) {
        if (root == null) {
            return;
        }
        Queue<BinaryTree> queue = new LinkedList<>();
        queue.add(root);
        BinaryTree lastNode = root;
        while (!queue.isEmpty()){
//            每次访问队列的第一个元素
            BinaryTree node = queue.poll();
            print(node.getValue());
//            左右节点不为空，则放入队列中
            if (node.getLeftNode() != null) {
                queue.add(node.getLeftNode());
            }
            if (node.getRightNode() != null) {
                queue.add(node.getRightNode());
            }
            if (linefeed) {
//                当前节点为最后一个节点，输出换行
                if(lastNode == node) {
                    System.out.println();
//                    下一个最后节点为当前节点的右节点，若为空则为左节点
                    if(node.getRightNode() != null){
                        lastNode = node.getRightNode();
                    } else {
                        lastNode = node.getLeftNode();
                    }
                }
            }
        }
    }

    /**
     * 获取树的层数
     * @param root
     * @return
     */
    public static int getLevel(BinaryTree root) {
        if (root == null) {
            return 0;
        }
//        层数为左子树和右子树的层数的最大值
        int leftLevel = 1 + getLevel(root.getLeftNode());
        int rightLevel = 1 + getLevel(root.getRightNode());
        return leftLevel > rightLevel ? leftLevel : rightLevel;
    }

    private static void print(Object value) {
        System.out.print(value + " ");
    }
}
